package msb.class06;


import common.sort.AbstractSort;
import msb.class01.Code01_SelectionSort;
import org.junit.Test;
import common.util.ArrayUtil;

import java.util.Arrays;
import java.util.Random;

/**
 * 荷兰国旗问题
 * 给定数组arr[0..N]
 * 以arr[N]为基准，  小于arr[N] 的数在左， 等于arr[N]的数在中间， 大于arr[N]的数在右边
 * 返回等于arr[N]的数的两个下标
 * <p>
 * 如[4,3,4,5,1,2,4] => [3,1,2,4,4,4,5]
 * 返回值 [3,5]
 */
public class Code02_partitionAndQuickSort extends AbstractSort {


    /**
     * 荷兰国旗
     *
     * @return
     */
    public int[] netherlandsFlag(int[] arr, int L, int R) {
        //左右边界
        int left = L;
        int right = R - 1;
        //当前指针
        int point = L;
        while (point <= right) {
            if (arr[point] < arr[R]) {
                ArrayUtil.swap(arr, point++, left++);
            } else if (arr[point] > arr[R]) {
                ArrayUtil.swap(arr, point, right--);
            } else {
                point++;
            }
        }
        ArrayUtil.swap(arr, R, ++right);
        return new int[]{left, right};
    }

    public int[] netherlandsFlagCheck(int[] arr, int L, int R) {
        int base = arr[R];
        int[] help = new int[R - L + 1];
        for (int i = 0; i < help.length; i++) {
            help[i] = arr[L + i];
        }
        Arrays.sort(help);

        int left = -1;
        int right = -1;
        for (int i = 0; i < help.length; i++) {
            if (left == -1 && help[i] == base) {
                left = i;
            }
            if (left != -1 && (help[i] > base || i == help.length - 1)) {
                if (help[i] > base) {
                    right = i - 1;
                    break;
                } else if (i == help.length - 1) {
                    right = i;
                    break;
                }
            }
        }
        return new int[]{left, right};
    }

    @Test
    public void checkNetherlandsFlag() {
        for (int i = 0; i < 100; i++) {
            int[] instant = ArrayUtil.instant(100, 100);
            int[] instantCopy = ArrayUtil.copy(instant);
            Code02_partitionAndQuickSort code = new Code02_partitionAndQuickSort();
            ArrayUtil.compare(
                    code.netherlandsFlag(instant, 0, instant.length - 1),
                    code.netherlandsFlagCheck(instantCopy, 0, instantCopy.length - 1));
        }
    }


    /**
     * 快速排序
     *
     * @param arr
     */
    public void sort(int[] arr) {
        if (arr.length == 1) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int random = L + new Random().nextInt(R - L + 1);
        ArrayUtil.swap(arr, random, R);
        int[] basePoints = netherlandsFlag(arr, L, R);
        process(arr, L, basePoints[0] - 1);
        process(arr, basePoints[1] + 1, R);
    }

    @Test
    public void testSort() {
        Code02_partitionAndQuickSort sort = new Code02_partitionAndQuickSort();
        sort.check();
    }
}
